Peneroka terawal di pulau itu mungkin orang budaya Lapita dari Kepulauan Solomon Tenggara atau kepulauan Vanuatu.[10] Menurut legenda Pohnpeian, pulau utama itu dicipta oleh sekumpulan 17 lelaki dan wanita dari tanah jauh ke selatan yang menimbun batu di terumbu karang sekitarnya. Pulau itu didiami oleh orang asli yang bercampur dengan pendatang baru. Bilangan mereka bertambah, tetapi masyarakat mereka berada dalam keadaan anarki yang berterusan.

Wangsa Saudeleur bermula dengan kedatangan ahli sihir kembar Olisihpa dan Olosohpa dari mitos Katau Barat, atau Kanamwayso. Olisihpa dan Olosohpa dikatakan jauh lebih tinggi daripada penduduk asli Pohnpeia. Saudara-saudara tiba dengan sampan besar mencari tempat untuk membina mezbah supaya mereka dapat menyembah Nahnisohn Sahpw, tuhan pertanian. Selepas beberapa permulaan palsu, dua beradik itu berjaya membina sebuah mezbah di Nan Madol megalitik, di mana mereka melakukan ritual mereka. Dalam legenda, saudara-saudara ini melayangkan batu-batu besar dengan bantuan naga terbang. Apabila Olisihpa meninggal dunia pada usia tua, Olosohpa menjadi Saudeleur pertama. Olosohpa mengahwini seorang wanita tempatan dan mengahwini dua belas generasi, menghasilkan enam belas penguasa Saudeleur lain dari klan Dipwilap ("Hebat").[note 3] Pengasas Wangsa memerintah dengan baik, walaupun pengganti mereka meletakkan permintaan yang semakin meningkat terhadap rakyat mereka.[5][9][11]